//给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符
//合要求的单词则返回空字符串。 
//
// 示例： 
//
// 输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
//输出： "dogwalker"
//解释： "dogwalker"可由"dog"和"walker"组成。
// 
//
// 提示： 
//
// 
// 0 <= len(words) <= 200 
// 1 <= len(words[i]) <= 100 
// 
// Related Topics 字符串 
// 👍 20 👎 0
#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_set>

using namespace std;


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    string longestWord(vector<string>& words) {
        unordered_set<string> allWords(words.begin(), words.end());
        string ans;
        for(auto word:words)
        {
            auto tmpCollects = allWords;
            tmpCollects.erase(word);
            if(isCombine(word,tmpCollects))
            {
                if (word.size() > ans.size())ans = word;
                if (word.size() == ans.size())ans = min(ans, word);
            }
        }
        return ans;
    }
    bool isCombine(string s,unordered_set<string>& words){
        if (s.size() == 0)return true;
        for(int i=1;i<=s.size();i++)
        {
            if (words.count(s.substr(0, i)) && isCombine(s.substr(i), words))return true;
        }
        return false;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
